var EventEmitter = require("events").EventEmitter
  , util = require("util")
  , misc = require("./misc")
  ;

function calcHoeffdingBound(range, e, n) {
  return Math.sqrt(- range * range * Math.log(e) / 2 / n);
}

function majorityClass(classStats) {
  return Object.keys(classStats).reduce(function (best, cur) {
    if (best) {
      return classStats[best] > classStats ? best : cur;
    } else {
      return cur;
    }
  });
}

util.inherits(HoeffdingTreeLearner, EventEmitter);

/**
 * Create a hoeffding tree learner.
 * 
 * @param param the parameters.
 */
function HoeffdingTreeLearner(param) {
  if (!(this instanceof HoeffdingTreeLearner)) {
    return new HoeffdingTreeLearner(param);
  }
  
  if (!param) {
    param = param || {};
  }
  
  this.tree = param.tree || {dataSet: []};
  this.bufferFeats = param.bufferFeats || 1;
  this.e = param.e || 0.01;
  this.t = param.t || 0.01;
}

/**
 * Learn from the feature vector. This method assumes that the last element of 
 * the vector is the actual label that could be used to learn.
 *
 * @param featVec the feature vector.
 * @return the predicted label of the feature vector.
 */
HoeffdingTreeLearner.prototype.learn = function (featVec) {
  var node = misc.sortToLeaf(this.tree, featVec);
  if (node.branch) {
    node = node.branch[featVec[node.attr]] = {dataSet: []};
  }
  node.dataSet.push(featVec);
  var classStats = node.dataSet.reduce(function (memo, featVec) {
    var label = featVec[featVec.length - 1];
    if (memo[label]) {
      memo[label] = 0;
    }
    memo[label] += 1;
    return memo;
  }, {});
  var classStatsCount = Object.keys(classStats).length;
  if (node.dataSet.length % this.bufferFeats === 0 && classStatsCount > 1) {
    var bestFeat = misc.calcInfoGains(node.dataSet).sort(function (a, b) {
      return a.infoGain < b.infoGain;
    });
    var hoeffdingBound = calcHoeffdingBound(
        Math.log(classStatsCount), this.e, node.dataSet.length);
    console.log(bestFeat[0].infoGain - bestFeat[1].infoGain + ':' + hoeffdingBound);
    if (bestFeat.length >= 2 
        && (bestFeat[0].infoGain - bestFeat[1].infoGain > hoeffdingBound
            || hoeffdingBound < this.t)) {
      node.branch = bestFeat[0].values.reduce(function (memo, cur) {
        memo[cur] = {dataSet: node.dataSet.filter(function (featVec) {
          return featVec[bestFeat[0].attr] == cur;
        })};
        return memo;
      }, {});
      node.attr = bestFeat[0].attr;
      delete node.dataSet;
      node.label = majorityClass(classStats);

      this.emit('splitted', JSON.stringify(this.tree));
    }
  }
  return node.label || majorityClass(classStats);
};

/**
 * Classify the given feature vector. The behavior is like learn() method 
 * but it didn't learn from the feature vector so it doesn't require a 
 * label as the last element of featVec.
 *
 * @param featVec the feature vector.
 * @return the predicted label.
 */
HoeffdingTreeLearner.prototype.classify = function (featVec) {
  var node = misc.sortToLeaf(this.tree, featVec);
  if (node.label) {
    return node.label;
  } else if (node.dataSet) {
    return misc.majorityCnt(node.dataSet);
  } else {
    return undefined;
  }
}

/**
 * Get the decision tree model from the learner.
 *
 * @return the decision tree model.
 */
HoeffdingTreeLearner.prototype.getTree = function () {
  return this.tree;
};

/**
 * Set the internal tree structure.
 *
 * @param the 
 */
HoeffdingTreeLearner.prototype.setTree = function (tree) {
  if (tree) {
    this.tree = tree;
  }
}

exports.HoeffdingTreeLearner = HoeffdingTreeLearner;

/**
 * Train the decision tree using the given dataset.
 * 
 * @param dataSet the data set.
 * @param param the hoeffding tree's parameter.
 * @return a decision tree model.
 */
function trainDecisionTree(dataSet, param) {
  var decisionTreeLearner = new HoeffdingTreeLearner(param);
  dataSet.map(decisionTreeLearner.learn.bind(decisionTreeLearner));
  return decisionTreeLearner.getTree();
}

exports.trainDecisionTree = trainDecisionTree;
